home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / index-rtree / rtget.c next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  7.4 KB  |  318 lines
  1. /*
  2.  *  rtget.c -- fetch tuples from an rtree scan.
  3.  */
  4. #include "tmp/c.h"
  5. #include "tmp/postgres.h"
  6.  
  7. #include "storage/bufmgr.h"
  8. #include "storage/bufpage.h"
  9. #include "storage/page.h"
  10.  
  11. #include "utils/log.h"
  12. #include "utils/rel.h"
  13.  
  14. #include "access/heapam.h"
  15. #include "access/genam.h"
  16. #include "access/iqual.h"
  17. #include "access/ftup.h"
  18. #include "access/rtree.h"
  19. #include "access/sdir.h"
  20.  
  21. RcsId("$Header: /private/postgres/src/access/index-rtree/RCS/rtget.c,v 1.6 1992/03/06 15:57:10 mao Exp $");
  22.  
  23. extern RetrieveIndexResult    rtscancache();
  24. extern RetrieveIndexResult    rtfirst();
  25. extern RetrieveIndexResult    rtnext();
  26. extern ItemPointer        rtheapptr();
  27.  
  28. RetrieveIndexResult
  29. rtgettuple(s, dir)
  30.     IndexScanDesc s;
  31.     ScanDirection dir;
  32. {
  33.     RetrieveIndexResult res;
  34.  
  35.     /* if we have it cached in the scan desc, just return the value */
  36.     if ((res = rtscancache(s, dir)) != (RetrieveIndexResult) NULL)
  37.     return (res);
  38.  
  39.     /* not cached, so we'll have to do some work */
  40.     if (ItemPointerIsValid(&(s->currentItemData))) {
  41.     res = rtnext(s, dir);
  42.     } else {
  43.     res = rtfirst(s, dir);
  44.     }
  45.     return (res);
  46. }
  47.  
  48. RetrieveIndexResult
  49. rtfirst(s, dir)
  50.     IndexScanDesc s;
  51.     ScanDirection dir;
  52. {
  53.     Buffer b;
  54.     Page p;
  55.     int n;
  56.     OffsetNumber maxoff;
  57.     RetrieveIndexResult res;
  58.     RTreePageOpaque po;
  59.     RTreeScanOpaque so;
  60.     RTSTACK *stk;
  61.     BlockNumber blk;
  62.     IndexTuple it;
  63.     ItemPointer ip;
  64.  
  65.     b = ReadBuffer(s->relation, P_ROOT);
  66.     p = BufferGetPage(b, 0);
  67.     po = (RTreePageOpaque) PageGetSpecialPointer(p);
  68.     so = (RTreeScanOpaque) s->opaque;
  69.  
  70.     for (;;) {
  71.     maxoff = PageGetMaxOffsetIndex(p);
  72.     if (ScanDirectionIsBackward(dir))
  73.         n = findnext(s, p, maxoff, dir);
  74.     else
  75.         n = findnext(s, p, 0, dir);
  76.  
  77.     while (n < 0 || n > maxoff) {
  78.  
  79.         ReleaseBuffer(b);
  80.         if (so->s_stack == (RTSTACK *) NULL)
  81.         return ((RetrieveIndexResult) NULL);
  82.  
  83.         stk = so->s_stack;
  84.         b = ReadBuffer(s->relation, stk->rts_blk);
  85.         p = BufferGetPage(b, 0);
  86.         po = (RTreePageOpaque) PageGetSpecialPointer(p);
  87.         maxoff = PageGetMaxOffsetIndex(p);
  88.  
  89.         if (ScanDirectionIsBackward(dir))
  90.         n = stk->rts_child - 1;
  91.         else
  92.         n = stk->rts_child + 1;
  93.         so->s_stack = stk->rts_parent;
  94.         free ((char *) stk);
  95.  
  96.         n = findnext(s, p, n, dir);
  97.     }
  98.     if (po->flags & F_LEAF) {
  99.         ItemPointerSet(&(s->currentItemData), 0, BufferGetBlockNumber(b),
  100.                 0, n + 1);
  101.  
  102.         it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
  103.         ip = (ItemPointer) palloc(sizeof(ItemPointerData));
  104.         bcopy((char *) &(it->t_tid), (char *) ip, sizeof(ItemPointerData));
  105.         ReleaseBuffer(b);
  106.  
  107.         res = ItemPointerFormRetrieveIndexResult(&(s->currentItemData), ip);
  108.  
  109.         return (res);
  110.     } else {
  111.         stk = (RTSTACK *) palloc(sizeof(RTSTACK));
  112.         stk->rts_child = n;
  113.         stk->rts_blk = BufferGetBlockNumber(b);
  114.         stk->rts_parent = so->s_stack;
  115.         so->s_stack = stk;
  116.  
  117.         it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
  118.         blk = ItemPointerGetBlockNumber(&(it->t_tid));
  119.  
  120.         ReleaseBuffer(b);
  121.         b = ReadBuffer(s->relation, blk);
  122.         p = BufferGetPage(b, 0);
  123.         po = (RTreePageOpaque) PageGetSpecialPointer(p);
  124.     }
  125.     }
  126. }
  127.  
  128. RetrieveIndexResult
  129. rtnext(s, dir)
  130.     IndexScanDesc s;
  131.     ScanDirection dir;
  132. {
  133.     Buffer b;
  134.     Page p;
  135.     int n;
  136.     OffsetNumber maxoff;
  137.     RetrieveIndexResult res;
  138.     RTreePageOpaque po;
  139.     RTreeScanOpaque so;
  140.     RTSTACK *stk;
  141.     BlockNumber blk;
  142.     IndexTuple it;
  143.     ItemPointer ip;
  144.  
  145.     blk = ItemPointerGetBlockNumber(&(s->currentItemData));
  146.     n = ItemPointerSimpleGetOffsetNumber(&(s->currentItemData)) - 1;
  147.  
  148.     if (ScanDirectionIsForward(dir))
  149.     ++n;
  150.     else
  151.     --n;
  152.  
  153.     b = ReadBuffer(s->relation, blk);
  154.     p = BufferGetPage(b, 0);
  155.     po = (RTreePageOpaque) PageGetSpecialPointer(p);
  156.     so = (RTreeScanOpaque) s->opaque;
  157.  
  158.     for (;;) {
  159.     maxoff = PageGetMaxOffsetIndex(p);
  160.     n = findnext(s, p, n, dir);
  161.  
  162.     while (n < 0 || n > maxoff) {
  163.  
  164.         ReleaseBuffer(b);
  165.         if (so->s_stack == (RTSTACK *) NULL)
  166.         return ((RetrieveIndexResult) NULL);
  167.  
  168.         stk = so->s_stack;
  169.         b = ReadBuffer(s->relation, stk->rts_blk);
  170.         p = BufferGetPage(b, 0);
  171.         maxoff = PageGetMaxOffsetIndex(p);
  172.         po = (RTreePageOpaque) PageGetSpecialPointer(p);
  173.  
  174.         if (ScanDirectionIsBackward(dir))
  175.         n = stk->rts_child - 1;
  176.         else
  177.         n = stk->rts_child + 1;
  178.         so->s_stack = stk->rts_parent;
  179.         pfree ((char *) stk);
  180.  
  181.         n = findnext(s, p, n, dir);
  182.     }
  183.     if (po->flags & F_LEAF) {
  184.         ItemPointerSet(&(s->currentItemData), 0, BufferGetBlockNumber(b),
  185.                 0, n + 1);
  186.  
  187.         it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
  188.         ip = (ItemPointer) palloc(sizeof(ItemPointerData));
  189.         bcopy((char *) &(it->t_tid), (char *) ip, sizeof(ItemPointerData));
  190.         ReleaseBuffer(b);
  191.  
  192.         res = ItemPointerFormRetrieveIndexResult(&(s->currentItemData), ip);
  193.  
  194.         return (res);
  195.     } else {
  196.         stk = (RTSTACK *) palloc(sizeof(RTSTACK));
  197.         stk->rts_child = n;
  198.         stk->rts_blk = BufferGetBlockNumber(b);
  199.         stk->rts_parent = so->s_stack;
  200.         so->s_stack = stk;
  201.  
  202.         it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
  203.         blk = ItemPointerGetBlockNumber(&(it->t_tid));
  204.  
  205.         ReleaseBuffer(b);
  206.         b = ReadBuffer(s->relation, blk);
  207.         p = BufferGetPage(b, 0);
  208.         po = (RTreePageOpaque) PageGetSpecialPointer(p);
  209.  
  210.         if (ScanDirectionIsBackward(dir))
  211.         n = PageGetMaxOffsetIndex(p);
  212.         else
  213.         n = 0;
  214.     }
  215.     }
  216. }
  217.  
  218. int
  219. findnext(s, p, n, dir)
  220.     IndexScanDesc s;
  221.     Page p;
  222.     int n;
  223.     ScanDirection dir;
  224. {
  225.     OffsetNumber maxoff;
  226.     IndexTuple it;
  227.     RTreePageOpaque po;
  228.     RTreeScanOpaque so;
  229.  
  230.     maxoff = PageGetMaxOffsetIndex(p);
  231.     po = (RTreePageOpaque) PageGetSpecialPointer(p);
  232.     so = (RTreeScanOpaque) s->opaque;
  233.  
  234.     /*
  235.      *  If we modified the index during the scan, we may have a pointer to
  236.      *  a ghost tuple, before the scan.  If this is the case, back up one.
  237.      */
  238.  
  239.     if (so->s_flags & RTS_CURBEFORE) {
  240.     so->s_flags &= ~RTS_CURBEFORE;
  241.     n--;
  242.     }
  243.  
  244.     while (n >= 0 && n <= maxoff) {
  245.     it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n));
  246.     if (po->flags & F_LEAF) {
  247.         if (ikeytest(it, s->relation, s->numberOfKeys, &s->keyData))
  248.         break;
  249.     } else {
  250.         if (ikeytest(it, s->relation, so->s_internalNKey,
  251.              &so->s_internalKey))
  252.         break;
  253.     }
  254.  
  255.     if (ScanDirectionIsBackward(dir))
  256.         --n;
  257.     else
  258.         ++n;
  259.     }
  260.  
  261.     return (n);
  262. }
  263.  
  264. RetrieveIndexResult
  265. rtscancache(s, dir)
  266.     IndexScanDesc s;
  267.     ScanDirection dir;
  268. {
  269.     RetrieveIndexResult res;
  270.     ItemPointer ip;
  271.  
  272.     if (!(ScanDirectionIsNoMovement(dir)
  273.           && ItemPointerIsValid(&(s->currentItemData)))) {
  274.  
  275.     return ((RetrieveIndexResult) NULL);
  276.     } 
  277.  
  278.     ip = rtheapptr(s->relation, &(s->currentItemData));
  279.  
  280.     if (ItemPointerIsValid(ip))
  281.     res = ItemPointerFormRetrieveIndexResult(&(s->currentItemData), ip);
  282.     else
  283.     res = (RetrieveIndexResult) NULL;
  284.  
  285.     return (res);
  286. }
  287.  
  288. /*
  289.  *  rtheapptr returns the item pointer to the tuple in the heap relation
  290.  *  for which itemp is the index relation item pointer.
  291.  */
  292.  
  293. ItemPointer
  294. rtheapptr(r, itemp)
  295.     Relation r;
  296.     ItemPointer itemp;
  297. {
  298.     Buffer b;
  299.     Page p;
  300.     IndexTuple it;
  301.     ItemPointer ip;
  302.     OffsetNumber n;
  303.  
  304.     ip = (ItemPointer) palloc(sizeof(ItemPointerData));
  305.     if (ItemPointerIsValid(itemp)) {
  306.     b = ReadBuffer(r, ItemPointerGetBlockNumber(itemp));
  307.     p = BufferGetPage(b, 0);
  308.     n = ItemPointerSimpleGetOffsetNumber(itemp);
  309.     it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n - 1));
  310.     bcopy((char *) &(it->t_tid), (char *) ip, sizeof(ItemPointerData));
  311.     ReleaseBuffer(b);
  312.     } else {
  313.     ItemPointerSetInvalid(ip);
  314.     }
  315.  
  316.     return (ip);
  317. }
  318.